// 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

// 示例 1:

// 输入: "aacecaaa"
// 输出: "aaacecaaa"
// 示例 2:

// 输入: "abcd"
// 输出: "dcbabcd"

#include "stdc++.h"

using namespace std;

/* 暴力法，超时
因为只能在字符串开头插入字符，可以从字符串开头找到最大的回文子串，然后反转剩余的字串放在前面
时间复杂度：O(N^2)
空间复杂度：O(N)
*/
class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        string rev{s};
        reverse(rev.begin(), rev.end());
        if (s == rev) return s; // s 本身就是回文串
        for (int i{0}; i < n; ++i) {
            if (s.substr(0, n - i) == rev.substr(i)) return rev.substr(0, i) + s;
        }
        return "";
    }
};

/* 双指针+递归
如果我们可以减小字符串的大小来搜索子字符串,而是不每次都检查完整的子字符串,就可以使该过程更加高效。
时间复杂度：O(N^2)
空间复杂度：O(N)
*/
class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        int i{0}; // 只需要在 [0,i) 范围内搜索
        for (int j{n-1}; j >= 0; --j) {
            if (s[i] == s[j]) ++i;
        }
        if (i == n) return s; // 整个字符串为回文串
        string remain_rev = s.substr(i, n);
        reverse(remain_rev.begin(), remain_rev.end());
        return remain_rev + shortestPalindrome(s.substr(0, i)) + s.substr(i);
    }
};

/* KMP
时间复杂度：O(N)
空间复杂度：O(N)
*/
class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        string rev{s};
        reverse(rev.begin(), rev.end());
        string s_new = s + "#" + rev;
        int n_new = s_new.size();
        vector<int> f(n_new, 0);
        for (int i{1}; i < n_new; ++i) {
            int t = f[i-1];
            while (t > 0 && s_new[i] != s_new[t]) t = f[t - 1];
            if (s_new[i] == s_new[t]) ++t;
            f[i] = t;
        }
        return rev.substr(0, n - f[n_new - 1]) + s;
    }
};